import java.util.*;

public class day3 {
    /**
     * NC147 主持人调度（二）
     * https://www.nowcoder.com/practice/4edf6e6d01554870a12f218c94e8a299?tpId=196&tqId=37562&ru=/exam/oj
     */
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        // 进行排序，根据 左端点进行排序，升序
        Arrays.sort(startEnd,(v1,v2) -> {
            return v1[0] <= v2[0] ? -1 : 1;
        });

        // 创建一个小根堆
        PriorityQueue<Integer> hash = new PriorityQueue<>(); // 默认为小根堆
        hash.offer(startEnd[0][1]); // 放入的都是 右端点的值，也就是结束时间
        for(int i = 1;i < n;i++) {
            // 查看一下堆顶元素
            int end = hash.peek();
            // 这个end就是最小的结束时间，之后比较一下 startEnd[i][0] 开始时间和 end比较，开始时间大于end就直接替换
            // 因为当 end结束的时候，主理人就可以在这个开始时间进行再次主持
            // 如果是 开始时间 小于 end 的话，那么需要新增一个主理人，也就是将其这个 开始时间的 结束时间入堆
            // 因为堆顶是 最小的结束时间，如果没有这个结束时间大，那么后面一定比其大
            if(startEnd[i][0] >= end) {
                hash.poll();
                hash.offer(startEnd[i][1]);
            }else {
                // 小于，直接添加一个
                hash.offer(startEnd[i][1]);
            }
        }
        // 最后 堆的 大小，就是主理人的人数
        return hash.size();
    }



    /**
     * AB20 走迷宫
     * https://www.nowcoder.com/practice/e88b41dc6e764b2893bc4221777ffe64?tpId=308&tqId=40477&ru=/exam/oj
     */
    public static int N = 1001;
    public static int n,m;
    public static int x1,y1,x2,y2;
    public static int[] dx = {0,0,1,-1};
    public static int[] dy = {1,-1,0,0};

    public static char[][] arr = new char[N][N];
    public static int[][] dist = new int[N][N]; // 判断这个位置是否是搜索过的，并且这个位置的最小步数是多少

    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        // 广度优先搜索，更适合用于 最小的次数问题，因为第一次遍历到的位置的步数一定是最小的
        n = in.nextInt();
        m = in.nextInt();
        x1 = in.nextInt();
        y1 = in.nextInt();
        x2 = in.nextInt();
        y2 = in.nextInt();

        for(int i = 1;i <= n;i++) {
            String str = in.next();
            for(int j = 1;j <= m;j++) {
                arr[i][j] = str.charAt(j - 1);
            }
        }
        System.out.println(bfs());
    }

    public static int bfs() {
        if(arr[x2][y2] == '*') {
            return -1;
        }
        // 对这个 dist 进行初始化
        for(int i = 1;i <= n;i++ ) {
            for(int j = 1;j <= m;j++) {
                dist[i][j] = -1;
            }
        }
        // 创建队列，进行 bfs 操作
        Queue<int[]> queue = new LinkedList<>();
        // 把第一个位置进行加入到队列中
        queue.add(new int[]{x1,y1});
        dist[x1][y1] = 0;

        // 进行 bfs 操作
        while(!queue.isEmpty()) {
            int[] t = queue.poll();
            int a = t[0],b = t[1];
            for(int k = 0;k < 4;k++) {
                int x = a + dx[k];
                int y = b + dy[k];
                if(x >= 1 && x <= n && y >= 1 && y <= m && arr[x][y] == '.' && dist[x][y] == -1) {
                    queue.add(new int[]{x,y});
                    dist[x][y] = dist[a][b] + 1;
                    if(x == x2 && y == y2) {
                        return dist[x][y];
                    }
                }
            }
        }
        return -1;
    }



    /**
     * kotori和气球
     * https://ac.nowcoder.com/acm/problem/50039
     */
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        // 排列组合问题：
        // 比如：n = 6  m = 5
        // 就是：6*5*5*5*5 -> 6*(m-1)个(n - 1)
        int ret = n;
        for(int i = 0;i < m - 1;i++) {
            ret = ret * (n - 1) % 109;
        }
        System.out.println(ret);
    }
}
